package pers.qianyu.month_202101.date_20210108;

import org.junit.*;

/**
 * 526. 优美的排列
 * https://leetcode-cn.com/problems/beautiful-arrangement/
 *
 * @author mizzle rain
 * @date 2021-01-08 20:18
 */
public class CountArrangement {
    public int countArrangement(int n) {
        int len = 1 << n;
        int[] dp = new int[len];
        dp[0] = 1;
        for (int i = 0; i < len; i++) {
            int index = 1;
            for (int j = 0; j < n; j++) {
                index += (i >> j) & 1;
            }
            for (int j = 1; j <= n; j++) {
                if ((((i >> j - 1) & 1) == 0) &&
                        ((index % j == 0) || (j % index == 0))) {
                    dp[i | (1 << j - 1)] += dp[i];
                }
            }
        }
        return dp[len - 1];
    }

    @Test
    public void test1() {
        int result = new CountArrangement().countArrangement(2);
        Assert.assertEquals(result, 2);
    }
}
